<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title></title>
	</head>
	<body>
	</body>
</html>
<script type="text/javascript">
	// var a = [1,null,2,3]
	// var rot;
	// function inorderTraversal  (root,arr=[]){
	// 	if(root){
	// 		inorderTraversal(root.left,arr)
	// 		arr.push(root.val)
	// 		inorderTraversal(root.right,arr)
	// 	}
	// 	console.log('arr',arr)
	// 	return arr
	// }
	// var c=	inorderTraversal(a)
	// console.log(c);
	
	//斐波拉契题(兔子生兔子题目)--从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子对数为多少
	// 产量分析：1， 1， 2， 3， 5， 8， 13， 21 。。。
	// 第n个月的兔子总数  =  第n-1个月的兔子总数 + 第n-2个月的兔子总数
	// 问题： 求任意月兔子的总数
	// function func( n )
	// {
	//     if (n == 0 || n == 1)
	//     {
	//         return 1;
	//     }
	//     return func(n-1) + func(n-2);
	// }
	
	// var b = func(3);
	// console.log(b);
	
	// 二分法
	var data =[1,2,3,4,5]
	function TwoFind(su){
		var length = data.length
		var start = 0
		var end = length-1 
		return find(start,end,su)
	}
	function find(start,end,su){
		
		// console.log('min',min)
		while(start < end){
			var min =Math.ceil((start+end)/2)
			if(su==data[min]){
				return min
			}else if(su>data[min]){
				start++
			}else{
				end--
			}
		}
		// if(su==data[min]){
		// 	return min
		// }else if(su>data[min] && end > start){
		// 	start++
		// 	return find(start,end,su)
		// }else if(su<data[min] && end > start){
		// 	end--
		// 	return find(start,end,su)
		// }else{
		// 	return null
		// }
		
	}
	var ar=TwoFind(5)
	// console.log('ar--',ar)
	
	// 单向链表
	var linkeList = function(){
		function Node(data){
			this.data=data
			this.next=null
		}
		this.length = 0
		this.head=null
		linkeList.prototype.add = function(data){
			var newNode = new Node(data)
			if(this.length == 0){
				this.head= newNode
			}else{
				var current = this.head
				while(current.next){
					current = current.next
				}
				
				current.next = newNode		
			}
			this.length++
		}
		linkeList.prototype.indexOf = function(data){
			var current = this.head
			var index = 0;
			while(current){
				if(current.data == data){
					return index
				}
				current=current.next
				index++
			}
			return -1
		}
		linkeList.prototype.removeAt = function(position){
			if(position<0 || position >=this.length ){
				return null
			}
			var current = this.head
			if(position == 0){
				this.head=this.head.next
			}else{
				var index = 0;
				var previous = null
				while (index < position){
					previous = current
					current=current.next
					index++
				}
				previous.next = current.next
				this.length--
				return current.data
			}
		}
		linkeList.prototype.toString = function(){
			var string=''
			var current = this.head
				while(current){
					string=string + '--'+current.data
					current = current.next
				}
			return string
		}
		linkeList.prototype.reveser = function(head){
			if(!head){
				return null
			}
			if(head.next == null){
			    return head
			}
			// var new_head=this.reveser(head.next);
			// //把当前节点连接到链表上
			// head.next.next=head; 
			// head.next=null;
			// return new_head;
			
			  let p1 = head;
			  let p2 = null;
			  while(p1) {
			    const tmp = p1.next;
			    p1.next = p2;
			    p2 = p1;
			    p1 = tmp;
			  }
			  return p2
			
		}
		linkeList.prototype.newList = function(){
			var current = this.head
			return current
		}
	}
	
	var linke = new linkeList()
	linke.add("aaa")
	linke.add("bbb")
	linke.add("ccc")
	// linke.removeAt(1)
	var newList = linke.newList()
	 console.log('TOSTRING',newList)
	 var c = linke.reveser(newList)
    console.log('TOSTRING',c )
	console.log('TOSTRING',linke.toString())
	

</script>